P와 NP 문제

풀기 쉬운 문제와 검증하기 쉬운 문제의 차이

문제의 난이도를 어떻게 말할 수 있을까?

P와 NP 문제는 알고리즘의 난이도를 다루는 계산 복잡도 이론(computational complexity theory)의 대표적인 주제이다. 여기서 관심 있는 것은 단순히 어떤 문제를 풀 수 있는지가 아니라, 얼마나 효율적으로 풀 수 있는가이다. 예를 들어 입력 크기를 n이라고 하자. 어떤 알고리즘의 실행 시간이 다음과 같다면,

O(n), \quad O(n^2), \quad O(n^3)

입력 크기가 커져도 비교적 통제 가능한 속도로 시간이 증가한다. 이런 시간을 다항시간(polynomial time)이라고 한다. 반면,

O(2^n), \quad O(n!)

같은 실행 시간은 입력 크기가 조금만 커져도 계산량이 매우 빠르게 증가한다. 그래서 계산 복잡도 이론에서는 보통 다항시간 안에 풀 수 있는 문제를 효율적으로 풀 수 있는 문제로 본다.

결정 문제

P와 NP는 보통 결정 문제(decision problem)에 대해 정의된다. 결정 문제는 답이 yes 또는 no로 나오는 문제이다.

예를 들어 최단 경로 문제를 생각해보자.

그래프에서 노드 s에서 노드 t까지 가는 최단 경로를 구하라.

이 문제 자체는 최적화 문제이다. 하지만 다음처럼 바꾸면 결정 문제가 된다.

그래프에서 노드 s에서 노드 t까지 길이가 k 이하인 경로가 존재하는가?

답은 yes 또는 no이다. 계산 복잡도 이론에서는 이런 식으로 문제를 결정 문제 형태로 바꾸어 다루는 경우가 많다.

P란 무엇인가?

P는 polynomial time의 약자이다. 어떤 결정 문제가 P에 속한다는 것은, 그 문제를 다항시간 안에 풀 수 있는 알고리즘이 존재한다는 뜻이다.

조금 더 수식적으로 쓰면, 입력 x의 길이를 n이라고 할 때 x가 어떤 문제 L의 yes-instance인지 여부를 다음 시간 안에 판별할 수 있으면,

O(n^k)

어떤 상수 k에 대해 그 문제는 P에 속한다고 말한다.

예를 들어 다음과 같은 문제들은 P에 속한다고 볼 수 있다.

• 정렬
• 그래프에서 최단 경로 찾기
• 최소 신장 트리 찾기
• 선형시스템 풀기

즉, P는 대략적으로 말하면 답을 효율적으로 찾을 수 있는 문제들의 집합이다.

NP란 무엇인가?

NP는 non-deterministic polynomial time의 약자이다. 여기서 주의할 점은 NP가 not polynomial의 약자가 아니라는 것이다. NP에 속한 문제는 답을 직접 빠르게 찾을 수 있다는 뜻이 아니다. 대신, 답의 후보가 주어졌을 때 그 후보가 맞는지 다항시간 안에 검증할 수 있다는 뜻이다. 즉, NP는 대략적으로 말하면 답을 빠르게 검증할 수 있는 문제들의 집합이다. 예를 들어 스도쿠를 생각해보자. 빈 칸이 많은 스도쿠 문제를 직접 푸는 것은 어려울 수 있다. 하지만 누군가 완성된 스도쿠 판을 주면, 그 답이 맞는지 확인하는 것은 비교적 쉽다.

• 각 행에 숫자가 한 번씩 나오는가?
• 각 열에 숫자가 한 번씩 나오는가?
• 각 3 \times 3 박스에 숫자가 한 번씩 나오는가?

이 조건들을 확인하면 된다. 즉, 답을 찾는 것은 어려워 보일 수 있지만, 답이 주어졌을 때 검증하는 것은 쉽다.

이를 조금 더 일반적으로 쓰면 다음과 같다. 어떤 문제 L이 NP에 속한다는 것은, x \in L임을 증명하는 certificate c가 존재하고, (x,c)를 다항시간 안에 검증할 수 있다는 뜻이다.

V(x,c) = \begin{cases} 1, & \text{if } c \text{ proves } x \in L \\ 0, & \text{otherwise} \end{cases}

여기서 V는 verifier이다. 중요한 점은 verifier가 다항시간 안에 실행되어야 한다는 것이다.

P와 NP의 관계

P에 속한 문제는 당연히 NP에도 속한다. 왜냐하면 문제를 다항시간 안에 풀 수 있다면, 주어진 답이 맞는지도 다항시간 안에 확인할 수 있기 때문이다. 따라서 다음 관계가 성립한다.

P \subseteq NP

하지만 반대 방향은 아직 모른다. 즉, 답을 빠르게 검증할 수 있는 모든 문제를 빠르게 풀 수도 있는지는 알려져 있지 않다.

이 질문이 바로 유명한 P vs NP 문제이다.

P \stackrel{?}{=} NP

직관적으로 말하면 다음 질문이다.

검증하기 쉬운 문제는 항상 풀기도 쉬운가?

현재까지는 이 질문에 대한 답은 모르고, 밀레니엄 문제로 등록되어 있다. 여담으로, P = NP인가에 대한 증명은 나오지 않았지만, 추측상 P \neq NP로 받아들여지는 추세로 알고있다.

NP-hard와 NP-complete

P와 NP를 공부하다 보면 NP-hard와 NP-complete라는 용어도 자주 등장한다. NP-hard는 NP에 속한 모든 문제만큼 어렵거나 그보다 더 어려운 문제를 말한다. NP-hard를 직관적으로 이해하려면 문제 번역기를 생각하면 된다. 어떤 문제 H가 NP-hard라는 것은, NP에 속한 여러 문제들을 H문제로 치환할 수 있다는 뜻이다. 예시로 들면 다음과 같다. 미로찾기와 한붓 그리기 게임이 서로 다른 게임처럼 보이지만, 이 문제들을 하나의 일반화된 문제 H로 치환할 수 있다면 H 문제는 해당 두 문제만큼 어렵거나 더 어려운 문제로 취급된다. 즉, 어떤 문제가 NP-hard라면, 그 문제를 효율적으로 풀 수 있을 때 NP에 속한 모든 문제도 효율적으로 풀 수 있게 된다.

NP-complete는 다음 두 조건을 모두 만족하는 문제이다.

1. 그 문제는 NP에 속한다.
2. 그 문제는 NP-hard이다.

즉, NP-complete 문제는 NP 안에 있으면서 NP에서 가장 어려운 문제들이다. 대표적인 NP-complete 문제로는 SAT(Boolean satisfiability problem)가 있다. SAT는 논리식이 주어졌을 때, 그 논리식을 참으로 만드는 변수 할당이 존재하는지 묻는 문제이다. 예를 들어 다음과 같은 논리식이 있다고 하자.

(x_1 \lor x_2) \land (\lnot x_1 \lor x_3)

SAT는 이 식을 참으로 만드는 x_1, x_2, x_3의 값이 존재하는지 묻는다. SAT가 중요한 이유는 최초로 NP-complete임이 증명된 문제이기 때문이다. 따라서 SAT를 다항시간 안에 풀 수 있다면, 모든 NP 문제를 다항시간 안에 풀 수 있다.

어떤 문제가 NP-complete라는 진단을 받으면, P=NP가 아닌 한 모든 instance를 다항시간 안에 정확하게 푸는 알고리즘은 기대하기 어렵다. 그래서 실제 알고리즘 설계에서는 다음 선택지를 검토하게 된다.

• exact solution을 포기하고 approximation algorithm을 쓴다.
• 항상 최적은 아니지만 빠르게 좋은 답을 주는 heuristic을 쓴다.
• 입력 크기가 작은 경우에만 exact algorithm을 사용한다.
• 문제의 특수한 구조를 가정해서 tractable한 subclass를 찾는다.

NP 주변에서 자주 나오는 복잡도 class

논문을 읽다 보면 P, NP, NP-hard, NP-complete만으로는 부족한 경우가 많다. 특히 알고리즘을 제안하거나 분석하는 논문에서는 exact computation이 어려운지, 병렬화가 가능한지, 특정 parameter를 고정하면 쉬워지는지 같은 질문을 자주 다룬다. 그래서 다음 용어들이 함께 등장한다.

#P

\#P는 “sharp P”라고 읽는다. NP가 yes/no를 묻는 decision problem을 다룬다면, \#P는 가능한 해의 개수를 세는 counting problem을 다룬다.

예를 들어 SAT는 다음을 묻는다.

이 논리식을 만족하는 assignment가 하나라도 존재하는가?

반면 #SAT는 다음을 묻는다.

이 논리식을 만족하는 assignment가 몇 개인가?

SAT는 decision problem이고, #SAT는 counting problem이다. 보통 counting은 existence보다 더 많은 정보를 요구한다. 그래서 어떤 문제가 \#P-hard라는 말은, 단순히 답이 존재하는지 판별하는 수준을 넘어 가능한 경우의 수나 합을 계산하는 어려움이 들어 있다는 뜻으로 이해하면 된다.

더 쉬운 예로 경로 문제를 생각할 수 있다. 두 지점 s와 t가 있을 때, decision problem은 다음처럼 묻는다.

s에서 t까지 갈 수 있는 경로가 존재하는가?

반면 counting problem은 다음처럼 묻는다.

s에서 t까지 갈 수 있는 경로가 모두 몇 개인가?

첫 번째 질문은 경로 하나만 찾으면 yes라고 답할 수 있다. 두 번째 질문은 가능한 경로들을 세어야 한다. 그래서 counting problem은 단순한 existence problem보다 더 많은 정보를 요구한다.

따라서 \#P-hard라는 진단은 “가능한 경우를 세거나 합산하는 exact computation 자체가 어렵다”는 신호가 된다. 이런 경우 논문에서는 제한된 입력 class를 찾거나, sampling, approximation, parameterized algorithm을 사용하는 방향으로 넘어가는 경우가 많다.

NC

NC는 병렬 계산에서 중요한 class이다. 이름은 Nick’s Class에서 왔고, Nicholas Pippenger의 이름을 딴 것으로 알려져 있다. Stephen Cook이 Pippenger의 병렬 계산 연구를 기리며 이 이름을 붙였다고 자주 설명된다.

NC에 속한다는 것은 대략 다음을 뜻한다.

polynomial number의 processor를 사용하면 poly-logarithmic time에 풀 수 있다.

여기서 poly-logarithmic time은 입력 크기 n에 대해 다음처럼 \log n의 다항식으로 표현되는 시간을 말한다.

O((\log n)^k)

예를 들어 NC^2는 대략 O((\log n)^2) depth의 병렬 circuit으로 풀 수 있는 문제 class를 뜻한다. 이 표현은 “일반적인 sequential algorithm이 무조건 빠르다”는 말이 아니다. 오히려 다음 의미에 가깝다.

충분한 병렬 자원을 쓸 수 있다면 계산 구조가 얕게 펼쳐질 수 있다.

예를 들어 여러 수의 합을 구하는 문제를 생각해보자. 한 processor가 왼쪽부터 차례대로 더하면 입력이 길어질수록 시간이 길어진다. 하지만 충분히 많은 processor가 있으면, 먼저 인접한 두 수씩 더하고, 그 결과를 다시 두 개씩 더하는 식으로 tree처럼 계산할 수 있다. 이 경우 계산 단계 수는 입력 개수 n에 대해 대략 \log n 수준으로 줄어든다. 이런 식으로 계산을 얕은 병렬 단계로 펼칠 수 있는지가 NC에서 중요한 관점이다.

그래서 어떤 문제가 NC에 속한다는 결과는 병렬화 가능성에 대한 좋은 신호이다. sequential time이 자동으로 작다는 뜻은 아니지만, 대규모 계산에서 parallel hardware를 활용할 수 있는 이론적 근거가 된다.

Parameterized complexity: FPT와 XP

어떤 문제는 전체 입력 크기만 보면 어렵지만, 특정 parameter가 작으면 풀 만해지는 경우가 있다. 예를 들어 그래프 문제에서는 treewidth, 경로 길이, 삭제할 vertex 수 같은 값이 parameter가 될 수 있다. 이런 관점을 parameterized complexity라고 한다.

입력 크기를 n, parameter를 k라고 하자.

FPT는 fixed-parameter tractable의 약자이다. 문제가 FPT라는 것은 실행 시간이 다음 형태로 bounded된다는 뜻이다.

f(k) \cdot n^c

여기서 f(k)는 parameter에만 의존하는 함수이고, c는 k와 무관한 상수이다. 즉 k가 작으면 f(k)가 크더라도, 입력 크기 n에 대해서는 항상 같은 차수의 polynomial time이 유지된다.

XP는 FPT보다 약한 class이다. XP에서는 실행 시간이 다음처럼 될 수 있다.

n^{f(k)}

즉 parameter k를 고정하면 polynomial time이지만, polynomial의 차수 자체가 k에 따라 커질 수 있다. 그래서 k가 조금만 커져도 실용적으로는 빠르지 않을 수 있다.

둘의 차이는 다음처럼 볼 수 있다.

Class	시간 형태	직관
FPT	f(k)n^c	parameter가 작으면 비교적 강한 tractability
XP	n^{f(k)}	parameter를 고정하면 polynomial이지만 차수가 커질 수 있음

예를 들어 어떤 그래프 문제에서 경로 길이 k를 parameter로 둔다고 하자. 문제가 XP에 들어간다면, k를 고정했을 때는 polynomial time algorithm이 있다는 뜻이다. 하지만 k가 커지면 polynomial의 차수가 함께 커질 수 있다. 반면 FPT라면, k에 의존하는 비용은 따로 분리되고 입력 크기 n에 대한 polynomial 차수는 고정된다. 그래서 parameter가 작은 상황에서는 FPT 결과가 XP 결과보다 더 강한 tractability를 의미한다.

FPT나 XP 결과는 “전체 문제는 어려워도, 어떤 parameter가 작으면 풀 수 있다”는 메시지를 준다. 예를 들어 특정 parameter가 작게 유지되는 입력 class를 다룬다면, hard problem이라도 실용적인 exact algorithm이 가능할 수 있다. 따라서 parameterized complexity는 단순히 어렵다/쉽다의 이분법보다 더 세밀한 진단을 제공한다.

정리

개념	의미
P	답을 다항시간 안에 찾을 수 있는 문제
NP	답이 주어졌을 때 다항시간 안에 검증할 수 있는 문제
NP-hard	NP의 모든 문제만큼 어렵거나 더 어려운 문제
NP-complete	NP에 속하면서 동시에 NP-hard인 문제
\#P	가능한 해의 개수나 합을 세는 counting problem class
NC	병렬 계산에서 poly-logarithmic time에 풀 수 있는 문제 class
FPT	parameter가 작을 때 f(k)n^c 형태로 풀리는 문제 class
XP	parameter를 고정하면 polynomial time이 되는 문제 class